package com.practice.bit;

/**
 * Basics: Java operator precedence
 * 1. postfix expr++, expr--
 * 2. unary ++expr, --expr, +expr, -expr, ~, !
 * 3. *, /, %
 * 4. +, -
 * 5. <<, >>, >>>
 * 6. <, >, <=, >=, instanceof
 * 7. ==, !=
 * 8. &
 * 9. ^
 * 10. |
 * 11. &&
 * 12. ||
 * 13. ?, :
 * 14. assignment =, +=, -=, *=, /=, %=, &=, |=, ^=, >>=, <<=, >>>=
 * 
 */
public class BitOperation {
	/**
	 * Given number n, count how many 1s in its binary form.
	 * 
	 * @param n
	 * @return
	 */
	public int count1s(int n) {
		int i = n;
		int count = 0;
		while (i != 0) {
			count += i & 1;
			i >>= 1;
		}
		return count;
	}
	
	public int count1sAnother(int n) {
		int count = 0;
		while (n > 0) {
			n = n & (n-1);
			count++;
		}
		return count;
	}
	
	/**
	 * Swap bit i and bit j in number n.
	 * 
	 * @param n
	 * @param i
	 * @param j
	 * @return
	 */
	public int swapBits(int n, int i, int j) {
		if ((n>>i & 1) == (n>>j & 1)) return n;
		int t = n ^ 1<<i;
		t ^= 1<<j;
		return t;
	}
	
	/**
	 * Swap odd bits with even bits.
	 * 
	 * @param n
	 * @return
	 */
	public int swapEvenOddBits(int n) {
		int mask1 = Integer.parseInt("1010101010101010", 2);
		int mask2 = Integer.parseInt("0101010101010101", 2);
		
		return (n & mask1) >> 1 | (n & mask2) << 1;
	}
	
	public int add(int a, int b) {
		if (b == 0) return a;
		return add(a ^ b, (a & b) << 1);
	}
	
	public int subtract(int a, int b) {
		if (b == 0) return a;
		return subtract(a ^ b, (~a & b) << 1);
	}
}
